package algorithm.leetcode.I101to200;

import algorithm.leetcode.TreeNode;

import java.util.Stack;

/**
 * 有点像Q94,不用递归的二叉树中序遍历
 */

public class Q173 {
}


class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        build(root);
    }

    public int next() {
        TreeNode pop = stack.pop();
        build(pop.right);
        // 不用担心build里面改变了pop的引用,build调用结束后方法JVM弹栈pop还是第23行的pop
        return pop.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    private void build(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}